package shujujiegou;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;


public class SkipList4<T> {
	public Node4<T> first;
	public Node4<T> last;
	public int length;
	public int height;//0��ʼ
	public Random r = new Random();
	public SkipList4() {
		last = new Node4<T>();
		last.key = Integer.MAX_VALUE;
		first = new Node4<T>();
		first.key = Integer.MIN_VALUE;
		first.next.add(last);
	}
	public void add(int key, T value){
		length++;
		//���ݽڵ��������õ��µĲ���
		if(getNewHeightBylength(length) > height) {
			height = getNewHeightBylength(length);
			
			first.next.add(last);
		}
		//����½ڵ�
		addNewNode(key, value);
	}
	public T get(int key) {
		if(getNode(key) == null) {
			return null;
		}
		return getNode(key).value;
	}
	public void delete(int key) {
		Node4<T> deleteNode = getNode(key);
		if(deleteNode == null) {
			System.out.println("key:"+key+"������");
			return;
		}
		for(int i = deleteNode.next.size()-1;i>=0;i--) {
			Node4<T> t = first;
			while(t.next.get(i).key != key){
				t = t.next.get(i);
			}
			t.next.set(i, deleteNode.next.get(i));
		}
		
		
		
	}
	
	
	
	private void addNewNode(int key, T value) {
		//������½ڵ�ĸ߶�
		int newNodeHeight = 0;
		for(int i=0;i<height;i++){
			if(r.nextBoolean()) {
				newNodeHeight++;
			}
		}
		//��ʼ���½ڵ�
		Node4<T> newNode = new Node4<T>();
		newNode.key = key;
		newNode.value = value;
		//�½ڵ�ĸ߶ȿ�ʼ����
		for(int i = newNodeHeight;i >= 0;i--){
			newNode.next.add(null);
 		}
		for(int i = newNodeHeight;i >= 0;i--){
			Node4<T> t = first;
			while(t.next.get(i).key < key) {
				t = t.next.get(i);
			}
			newNode.next.set(i, t.next.get(i));
			t.next.set(i, newNode);		
 		}
	}
	
	
	
	private Node4<T> getNode(int key) {
		int tempHeight = height;
		Node4<T> t = first;
		for(int i=tempHeight;i>=0;i--) {
			while(t.next.get(i).key <= key) {
				t = t.next.get(i);
			}
			if(t.key == key) {
				return t;
			}
		}
		
		return null;
	}
	
	//lengthΪ2ʱ->1   4->2   8->3
	private int getNewHeightBylength(int length) {
		return (int) (log2(length));
	}
	private double log2(int a) {
		return Math.log(a)/Math.log(2);
	}
	
}
class Node4<T> {
	public List<Node4<T>> next;//�±��ʾ�ڼ���  ָ����һ���ڵ�
	public int key;
	public T value;
	public Node4() {
		next = new ArrayList<Node4<T>>();
	}
	
	
}